package disclog;

import java.math.BigInteger;

public class Shank {


	public static long shank(long p, long alpha, long beta)
	{
		long m = (long)(Math.ceil(Math.sqrt(p)));
		BigInteger m1 = BigInteger.valueOf(m);
		BigInteger p1 = BigInteger.valueOf(p);
		BigInteger alphaM = BigInteger.valueOf(alpha).modPow(m1, p1);
		BigInteger alphaInv = BigInteger.valueOf(alpha).modInverse(p1);
		BigInteger beta1 = BigInteger.valueOf(beta);
		long r = -1;
		long t = -1;
		long Alpha[] = new long[(int) m];
		
		for(int i = 1; i < m; ++i)
			Alpha[i] = alphaM.modPow(BigInteger.valueOf(i), p1).longValue();
		
		for(int i = 1; i < m; ++i)
		{
			BigInteger bi = alphaInv.modPow(BigInteger.valueOf(i), p1);
			long b = bi.multiply(beta1).mod(p1).longValue();
			
			for(int j = 1; j < m; ++j)
			{
				if(b == Alpha[j])
				{
					r = i;
					t = j;
				}
			}
		}
		
		return ((m * t) + r) % p;
			
	}
	
	public static void main(String[] args) {
		System.out.println(shank(2579, 2, 131));
		System.out.println(shank(809, 3, 525));
	}

}
